package com.leetcode.algorithm.y18.m05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode-cn.com
 * 434. 字符串中的单词数
 * 438. 找到字符串中所有字母异位词
 * @author: jie.deng
 * @time: 2018年5月22日 上午9:13:50
 */
public class MySolution0522 {
	
	/**
	 * 434. 字符串中的单词数
	 * 统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
	 * 
	 * 请注意，你可以假定字符串里不包括任何不可打印的字符。
	 * 
	 * 示例:
	 * 输入: "Hello, my name is John" 
	 * 输出: 5
	 * 
	 * @param s
	 * @return
	 */
    public int countSegments(String s) {
    	if ("".equals(s.trim())) {
			return 0;
		}
    	return s.trim().split("\\s+").length;
    }
   
    /**
	 * 438. 找到字符串中所有字母异位词
	 * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
	 * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
	 * 
	 * 说明：
	 * 字母异位词指字母相同，但排列不同的字符串。 
	 * 不考虑答案输出的顺序。 
	 * 
	 * 示例 1:
	 * 输入: s: "cbaebabacd" p: "abc"
	 * 输出: [0, 6]
	 * 解释: 
	 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 
	 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。 
	 * 
	 * 示例 2:
	 * 输入: s: "abab" p: "ab"
	 * 输出: [0, 1, 2]
	 * 解释: 
	 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 
	 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 
	 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
	 * 
	 * @param s
	 * @param p
	 * @return
	 */
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> list = new ArrayList<Integer>();

		char[] charS = s.toCharArray();
		int lenS = charS.length;
		char[] charP = p.toCharArray();
		int lenP = charP.length;
		Arrays.sort(charP);
		int i = 0;
		outer: while (i <= lenS - lenP) {
			for (int j = 0; j < lenP; j++) {
				if (p.indexOf(charS[i + j]) == -1) {
					i = i + j + 1;
					continue outer;
				}
			}
			char[] subCharS = Arrays.copyOfRange(charS, i, i + lenP);
			Arrays.sort(subCharS);
			if (Arrays.equals(charP, subCharS)) {
				list.add(i);
				i++;
				while (i <= lenS - lenP && charS[i - 1] == charS[i + lenP - 1]) {
					list.add(i);
					i++;
				}
			} else {
				i++;
				if (i < lenS - lenP && p.indexOf(charS[i + lenP - 1]) == -1) {
					i = i + lenP;
				}
			}
		}

		return list;
	}
    
}
